package com.tucc.hello.leetcode.no1_400.no1_200.no41_60.no44;

import java.util.LinkedHashMap;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        String s = "adceb";
        String p = "*a*?b";
        //
//        s = "aaaabaaaabbbbaabbbaabbaababbabbaaaababaaabbbbbbaabbbabababbaaabaabaaaaaabbaabbbbaababbababaabbbaababbbba";
//        p = "*****b*aba***babaa*bbaba***a*aaba*b*aa**a*b**ba***a*a*";
//
//        s = "abbabaaabbabbaababbabbbbbabbbabbbabaaaaababababbbabababaabbababaabbbbbbaaaabababbbaabbbbaabbbbababababbaabbaababaabbbababababbbbaaabbbbbabaaaabbababbbbaababaabbababbbbbababbbabaaaaaaaabbbbbaabaaababaaaabb";
//        p = "**aa*****ba*a*bb**aa*ab****a*aaaaaa***a*aaaa**bbabb*b*b**aaaaaaaaa*a********ba*bbb***a*ba*bb*bb**a*b*bb";
        System.out.println(solution.isMatch(s, p));
    }

    final static char ANY = '?';

    final static char MORE = '*';

    public boolean isMatch(String s, String p) {
        int sl = s.length();
        int pl = p.length();
        boolean[][] dp = new boolean[sl + 1][pl + 1];
        dp[0][0] = true;
        int i = 0;
        // p的前i个规则如果都是* 则用s的0个字符就可以和前i个规则匹配
        while (++i <= pl) {
            if (p.charAt(i - 1) == MORE) {
                dp[0][i] = true;
            } else {
                break;
            }
        }
//        printArr(dp);
        for (i = 1; i <= sl; i++) {
            char ch = s.charAt(i - 1);
            for (int j = 1; j <= pl; j++) {
                char pat = p.charAt(j - 1);
                if (pat == MORE) {
                    // 当前规则为任意
                    // 此时取决于 前i个字符能否和 前j-1个规则匹配 或者 前i-1个字符能否和 j个规则匹配
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                } else if (ANY == pat || pat == ch) {
                    // 当前字符匹配 则取决于前 i-1个字符和 前j-1个规则 能否匹配
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
//        printArr(dp);
        return dp[sl][pl];
    }

    private void printArr(boolean[][] arr) {
        System.out.println("===================");
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println("===================");
    }

}
